package cn.big.algs.learn.sort;

/**
 * 冒泡排序
 * 两个数比较大小，较大的数下沉，较小的数冒起来。平均时间复杂度 O(n2)
 *
 * @author LiJianXin
 * @create 2020/4/22 0022
 */
public class BubbleSort {
	public static void main(String[] args) {
		int number = 100000;
		long start = System.nanoTime();
		for (int i = 0; i < number; i++) {
			bubbleSort();
//			bubbleSort2();
		}
		System.out.println("平均计时时：" + (System.nanoTime() - start) / number);
	}

	/**
	 * 普通冒泡排序
	 */
	private static void bubbleSort() {
		int[] arr = new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
		for (int i = 0, size = arr.length; i < size - 1; i++) {
			for (int j = i + 1; j < size; j++) {
				if (arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		for (int i : arr) {
			System.out.print(i + ",");
		}
		System.out.println();
	}

	/**
	 * 优化后
	 */
	private static void bubbleSort2() {
		int[] arr = new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
		for (int i = 0, size = arr.length; i < size - 1; i++) {
			//优化，当没有进行换位时，不需要再进行循环
			boolean flag = false;
			for (int j = i + 1; j < size; j++) {
				if (arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
					flag = true;
				}
			}
			if (!flag) break;
		}
		for (int i : arr) {
			System.out.print(i + ",");
		}
		System.out.println();
	}
}
